perm filename GEOM0[3,BGB] blob
sn#116889 filedate 1974-08-27 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00011 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 {⊂C<NF3αGEOMED.λ30P27I425,0JCFA} SECTION 3.
C00006 00003
C00011 00004 {JC} FIGURE 3.2 - THE 24 DISPLAYS OF EXAMPLE #2. {I∂65,80X0.152H2
C00015 00005 In example #2, the model of an actual robot arm is read in
C00017 00006 ⊂3.1 Euler Primitives.⊃
C00023 00007
C00025 00008 {I175,0FCJC} FIGURE 3.3 - FIVE KINDS OF NON-SOLID POLYHEDRA.{H2
C00027 00009 Example 3 - Make Hexahedron.{λ7W100,1260,0,1900JAF3}
C00029 00010
C00031 00011
C00034 ENDMK
C⊗;
{⊂C;<N;F3;αGEOMED.;λ30;P27;I425,0;JCFA} SECTION 3.
{JCFD} A GEOMETRIC MODELING SYSTEM.
{λ10;W250;JAFA}
3.0 Introduction to GEOMED.
3.1 Euler Primitives.
3.2 Routines using Euler Primitives.
3.3 Euclidean Routines.
3.4 Image Synthesis: Perspective Projection and Clipping.
3.5 Image Analysis: Interface to CRE.
{λ30;W0;I950,0;JUFA}
⊂3.0 Introduction to GEOMED.⊃
GEOMED (Geometric Editor) is a system of subroutines for
manipulating winged edge polyhedra. The system has two
manifestations: first, it appears as an interactive 3-D drawing
program and second, it appears as a geometric modeling command
language. It is the latter manifestation along with some of the
details of implementation that is the subject of this chapter; the
interactive drawing program is documented in (Baumgart 74). As a
language, GEOMED is all semantics with no particular syntax of its
own; there are about two hundred subroutines which take from zero to
four arguments, return one or no values and which usually have
considerable side effects on the data structures. The subroutines
can be grouped into five classes: utility routines, Euler routines,
Euclidean routines, image synthesis and image analysis routines. The
utility routines include input/output, trigonometric functions,
memory management, a command scanner, and device dependent display
routines; the utility routines will not be further elaborated. The
Euler routines perform topological operations on links, the
Euclidean routines perform geometric computations on data, and the
image synthesis routines perform photographic simulations on the
model as a whole. The fifth class, image analysis routines,
consists at present solely of an interface between GEOMED and CRE,
the fifth group lacks the completeness of the other parts of the system.
As in the previous chapter, the programming notation used
will continue to have an ALGOL appearance with specific examples of
actual GEOMED code being given in the language SAIL (Stanford ALGOL)
as is example #1 immediately below. The program in example #1 creates
two cubic prisms and
{λ7;W100;JAF3}
BEGIN "EXAMPLE ONE"
REQUIRE "GEOMES.HDR[GEM,HE]" SOURCE_FILE; COMMENT DECLARE GEOMED EMBEDDED IN SAIL;
DEFINE PI="3.1415927";
INTEGER B1,B2,I; COMMENT TWO BODIES AND AN IMAGE COUNTER;
MKUNIV; COMMENT INITIALIZE THE DATA STRUCTURES;
B1 ← MKCUBE(8,1,0.5); COMMENT CREATE A COUPLE OF CUBIC PRISMS;
B2 ← MKCUBE(1,2,4);
TRANSL(B2,-7,1.5,0); COMMENT DISPLACE ONE OF THEM;
FOR I←1 STEP 1 THRU 24 DO COMMENT MAKE 24 IMAGES;
BEGIN
GEODPY; COMMENT DISPLAY REFRESH;
PLOTO("TMP."&CVS(I)); COMMENT OUTPUT LATEST DISPLAY TO DISK;
ROTATE(B1,PI/10,PI/12,PI/13); COMMENT ACTION WITH RESPECT TO ...;
ROTATE(B2,0,2*PI/23,0); COMMENT ...WORLD COORDINATES;
END;
END "EXAMPLE ONE";{λ30;W0;JUFA;}
{JC} FIGURE 3.1 - THE 24 DISPLAYS OF EXAMPLE #1.{I∂65,80;X0.152;H2;
*PLTX1.1;I∂0,∂156;*PLTX1.2;I∂0,∂156;*PLTX1.3;I∂0,∂156;*PLTX1.4;I∂0,∂156;
*PLTX1.5;I∂0,∂156;*PLTX1.6;I∂0,∂156;*PLTX1.7;I∂0,∂156;*PLTX1.8;I∂0,∂156;I∂130,80;
*PLTX1.9;I∂0,∂156;*PLTX1.10;I∂0,∂156;*PLTX1.11;I∂0,∂156;*PLTX1.12;I∂0,∂156;
*PLTX1.13;I∂0,∂156;*PLTX1.14;I∂0,∂156;*PLTX1.15;I∂0,∂156;*PLTX1.16;I∂0,∂156;I∂130,80;
*PLTX1.17;I∂0,∂156;*PLTX1.18;I∂0,∂156;*PLTX1.19;I∂0,∂156;*PLTX1.20;I∂0,∂156;
*PLTX1.21;I∂0,∂156;*PLTX1.22;I∂0,∂156;*PLTX1.23;I∂0,∂156;*PLTX1.24;I∂0,∂156;I∂65,0;}
\displays them rotating. The header file, GEOMES.HDR, is kept on a
disk area [GEM,HE] and contains the names of the necessary load
modules, the declarations of all the modeling routines and SAIL
macros for accessing GEOMED data structures. After the header, the
first routine to execute is MKUNIV (make universe), which initializes
the data structures. Next two polyhedra are created using the MKCUBE
routine which takes three arguments: width, breadth and height for
specifying a rectangular right parallelepiped. All such creation
routines return an integer which is the machine address of the node
of the entity created. The first routine of the FOR-loop is GEODPY
which refreshes the display of the model. Finally, the example calls
TRANSL and ROTATE which perform translation and rotation. TRANSL
takes four argument: the thing to be moved followed by the three
components of a translation vector; similarly ROTATE takes four
arguments: the thing to be moved followed by the three components of
a rotation vector; there are several other ways to specify
translation and rotation.
{JC} FIGURE 3.2 - THE 24 DISPLAYS OF EXAMPLE #2. {I∂65,80;X0.152;H2;
*PLTX2.1;I∂0,∂156;*PLTX2.2;I∂0,∂156;*PLTX2.3;I∂0,∂156;*PLTX2.4;I∂0,∂156;
*PLTX2.5;I∂0,∂156;*PLTX2.6;I∂0,∂156;*PLTX2.7;I∂0,∂156;*PLTX2.8;I∂0,∂156;I∂130,80;
*PLTX2.9;I∂0,∂156;*PLTX2.10;I∂0,∂156;*PLTX2.11;I∂0,∂156;*PLTX2.12;I∂0,∂156;
*PLTX2.13;I∂0,∂156;*PLTX2.14;I∂0,∂156;*PLTX2.15;I∂0,∂156;*PLTX2.16;I∂0,∂156;I∂130,80;
*PLTX2.17;I∂0,∂156;*PLTX2.18;I∂0,∂156;*PLTX2.19;I∂0,∂156;*PLTX2.20;I∂0,∂156;
*PLTX2.21;I∂0,∂156;*PLTX2.22;I∂0,∂156;*PLTX2.23;I∂0,∂156;*PLTX2.24;I∂0,∂156;I∂65,0;
λ7;W200;JAF3;}
BEGIN "EXAMPLE TWO"
REQUIRE "GEOMES.HDR[GEM,HE]" SOURCE_FILE; αα GEOMED EMBEDDED IN SAIL;
DEFINE αα="COMMENT"; DEFINE PI="3.1415927"; αα DECLARE COMMENT PREFIX;
INTEGER B1,B2,J1,J2,J3,J4,J5,J6,C1,CHR,I;
MKUNIV;GEODPY;
B1 ← INB3D("ARM[DAT,BGB]"); αα MODEL OF THE YELLOW ARM;
B2 ← INB3D("TABLE[DAT,BGB]"); αα MODEL OF THE HAND/EYE TABLE;
J1 ← FDNAME("JOINT1"); αα SHOULDER - ABOUT VERTICAL;
J2 ← FDNAME("JOINT2"); αα ARM - ABOUT HORIZONTAL;
J3 ← FDNAME("JOINT3"); αα SLIDE;
J4 ← FDNAME("JOINT4"); αα WRIST TWIST;
J5 ← FDNAME("JOINT5"); αα WRIST FLAP;
J6 ← FDNAME("JOINT6"); αα HAND;
C1 ← INCAM("ARMCAM[DAT,BGB]"); αα INPUT A PARTICULAR CAMERA MODEL;
FOR I←1 STEP 1 UNTIL 24 DO αα TWENTY FOUR IMAGES FOR FIGURE 3.2;
BEGIN
SHOW2(0,0); αα HIDDEN LINE ELIMINATION DISPLAY REFRESH;
PLOTO("PLTX2."&CVS(I)); αα OUTPUT LATEST DISPLAY FILE TO DISK;
ROTATE(-J1,0,0,PI/40); αα ACTION WITH RESPECT TO BODY COORDIATES...;
ROTATE(-J2,0,0,-PI/80); αα ...WHEN BODY ARGUMENT IS GIVEN NEGATIVE;
TRANSL(-J3,0,0,0.06);
END;
END "EXAMPLE TWO";{λ30;W0;JUFA;}
In example #2, the model of an actual robot arm is read in
and the first three joints are run through a simulated arm motion.
The routine INB3D reads a B3D polyhedron file from the disk. The arm
was drawn from measurements using the interactive form of GEOMED. The
FDNAME, find name, routine retrieves a body by its print name;
FDNAME returns zero when a name is not found. The routine INCAM reads
in a camera file. Finally, the routine SHOW2 calls the hidden line
eliminator; when SHOW2's arguments are zero, default options are
assumed. The arm model was originally made to illustrate an arm
trajectory for a thesis on arm control (Paul 69) and has been used
two times since in projects concerning arm trajectory planning and
arm collision avoidance.
GEOMED is a hierarcy of several levels of routines that are
finally invoked by syntactically trivial subroutine calls. The point
illustrated by the examples is that some applications level GEOMED
code has a quite ordinary appearance that does not require mastery of
the many underlying primitives which are explained in the next
several sections.
⊂3.1 Euler Primitives.⊃
The Euler routines are based on the idea that an
arbitrary polyhedron can be created in steps that always maintain the
Euler relation: F-E+V=2*(B-H). Topologically, a connected
Eulerian polyhedral graph can be built up with only four creation
primitives: MKBFV, MKEV, MKFE and GLUEE or taken apart with four
kill primitives: KLBFEV, KLEV, KLFE and UNGLUEE. The prefixes "MK"
and "KL", stand for <make> and <kill>; the initials "B", "F", "E"
and "V" invariably stand for <body, face, edge> and <vertex> and
tend to appear in that order. The notion of <GLUE> is associated with
the process of forming (or removing) a handle which increases (or
decreases) the topological genus of the surface by one unit. The
MKBFV primitive takes no arguments and creates a degenerate point
polyhedron of one vertex, one face and one body which is the minimal
non-zero binding satisfying the Euler relation. The MKEV creates a
new edge and a new vertex, the new edge is attached to the old vertex
as a spur in the perimeter of the given face. The MKFE creates a new
face and a new edge, the new edge is placed between the two given
vertices. And the GLUEE routine creates a handle or kills a body node
by placing a new edge between two given vertices and by removing the
second of two given faces. Completing the set, the ESPLIT routine
(explained in Section 2.5) is included as a form of MKEV.
In principle, the advantages of the pure Euler primitives are
that they assure valid topology, full generality, reasonable
simplicity and they achieve a semantic level slightly higher than
that of manipulating the nodes and links directly.
However, the Euler primitives only satisfy the first of the
conditions defining a solid polyhedron; imposing no particular
restrictions on surface orientation, face/vertex trivalence, face
planarity, face convexity or surface self intersection. Furthermore,
even some low level topological operations (such as body
intersection, Chapter 5) are inconvenient to specify in term of the
Euler primitives. Nevertheless in practice, the Euler primitives
perform a useful role as a topological foundation for coding routines
which embody more algebra and geometry and which lead to higher
semantic levels.{|;λ10;JAFA}
BOX 3.1 {JC;T100,200,700;} THE EULER PRIMITIVES.
EULER MAKE PRIMITIVES:
1. BNEW ← MKBFV; Makes point polyhedron.
2. VNEW ← MKEV(F,V); Makes new edge and vertex.
VNEW ← ESPLIT(E); Makes new edge and vertex.
3. ENEW ← MKFE(V1,F,V2); Makes new face and edge.
4. ENEW ← GLUEE(F1,V1,F2,V2); Makes new edge, kills F2,
and makes a hole or kills a body.
EULER KILL PRIMITIVES:
1. QNEW ← KLBFEV(Q); Kills bodies, faces, edge and vertices.
2. FACE ← KLFE(E); Kills E and NFACE(E). Returns PFACE(E).
3. EDGE ← KLEV(V); Kills V and PED(V). Returns other E of V.
VERT ← KLEV(E); Kills E and NVT(E). Returns PVT(E).
4. FNEW ← UNGLUE(E); Kills E, makes F. Returns the new face,
and kills a hole or makes a body.
{|;λ30;T-1;JU;FA}
The remainder of this section consists of more
explanation and examples of the Euler primitives and may be skipped
by the reader who does not need an elaboration of this level of
modeling. <Non-solid polyhedra>: Intermediate between Eulerian and
solid polyhedra are the wire, dangling-wire (or spur), lamina,
sheet and wasp-edged polyhedra which are transition states for
creating and altering polyhedral solids. The <wire> polyhedron
consists of one face, N edges and N+1 vertices. A <lamina> is a two
faced polyhedron with no interior edges or dangling wire. A
<dangling wire> or <spur> is made when a MKEV is applied to a vertex
of an already closed simply connected face perimeter; dangling wire
spurs are ultimately "closed" or "tied down" by a MKFE application. A
<sheet> is an array of lamina, with the exception of ruled surfaces of
rotation, commands for folding and manipulating sheets have not been
developed. Finally, a <wasp> polyhedron is a transition state formed by
the GLUEE primitive; this degenerate polyhedron is named for the wasp
waisted face perimeter which (like a spur) is eliminated by
appropriate MKFE applications.{Q}
{I175,0;FCJC} FIGURE 3.3 - FIVE KINDS OF NON-SOLID POLYHEDRA.{H2;
X0.246;JAFA;I∂0,0;⊗33.1;
I∂0,∂252;⊗33.2;I∂0,∂252;⊗33.3;I∂0,∂252;⊗33.4;I∂0,∂252;⊗33.5;
I∂250,10;}WIRE{I∂0,10+252;}LAMINA{I∂0,10+2*252;}DANGLING WIRE{
I∂0,10+3*252;}SHEET{I∂0,10+4*252;}WASP WAIST{I∂30,0;JUFA}
The use of the Euler primitives is limited to the above
transition states. MKEV sweeps a MKBFV point body into a wire, the
wire may be continued (at only its newest end) by additional MKEVs
until it is closed into a lamina by MKFEing the first and last
vertices of the wire. The MKFE is oriented such that if the wire is
planar and the resulting lamina is homogeneous
(non-self-intersecting); then the exterior vector of the newly
created face points into the counter clockwise halfspace of the
lamina, the halfspace from which the order of creation of the
vertices appears to be counter clockwise. This particular generation
by Euler sweeping from point, through wire and lamina, to solid is
illustrated by the make hexahedron example #3 and by the make
tetrahedron example #4; the final example of this section, example
#5, illustrates the use of GLUEE.
Example 3 - Make Hexahedron.{λ7;W100,1260,0,1900;JAF3}
BEGIN "EXAMPLE THREE"
REQUIRE "GEOMES.HDR[GEM,HE]" SOURCE_FILE; αα GEOMED EMBEDDED IN SAIL;
INTEGER PROCEDURE MAKECUBE(REAL DX,DY,DZ);
BEGIN "MAKECUBE"
INTEGER B,F,E,V1,V2,V3,V4;
DEFINE αα="COMMENT"; αα COMMENT DELIMITER;
αα MAKE RECTANGULAR LAMINA;
B ← MKBFV; F ← PFACE(B); V1 ← PVT(B); αα MAKE POINT POLYHDERA;
XWC(V1) ← DX/2; YWC(V1) ← DY/2; ZWC(V1) ←-DZ/2; αα POSITION FIRST VERTEX;
V2 ← MKEV(F,V1); XWC(V2) ← -DX/2; αα MAKE AND POSITION 2ND VERTEX;
V3 ← MKEV(F,V2); YWC(V3) ← -DY/2; αα MAKE AND POSITION 3RD VERTEX;
V4 ← MKEV(F,V3); XWC(V4) ← DX/2; αα MAKE AND POSITION 4TH VERTEX;
MKFE(V1,F,V4); F ← PFACE(F);
αα MAKE FOUR SPURS ON THE LAMINA;
V1 ← MKEV(F,V1);V2 ← MKEV(F,V2);
V3 ← MKEV(F,V3);V4 ← MKEV(F,V4);
ZWC(V1) ← ZWC(V2) ← ZWC(V3) ← ZWC(V4) ← DZ/2; αα POSITION LAST FOUR VERTICES;
αα JOIN SPURS TO FORM FINAL FACE;
MKFE(V1,F,V2); MKFE(V2,F,V3);
MKFE(V3,F,V4); MKFE(V4,F,V1);
RETURN(B);
END "MAKECUBE";
MKUNIV; MAKECUBE(10,8,6); αα TEST CALL ON MAKECUBE;
END "EXAMPLE THREE";{λ30;W0,1260,0,1900;JUFA;Q}
Example 4 - Make Regular Tetrahedron.{λ7;W100;JAF3}
BEGIN "EXAMPLE FOUR"
REQUIRE "GEOMES.HDR[GEM,HE]" SOURCE_FILE; αα GEOMED EMBEDDED IN SAIL;
DEFINE αα="COMMENT";DEFINE PI="3.1415927";
INTEGER PROCEDURE MKTETRA (REAL R); αα MAKE TETRAHEDRON;
BEGIN "MKTETRA"
INTEGER B,F1,F2,V1,V2,V3,V4;
B ← MKBFV; F1 ← PFACE(B); V1 ← PVT(B); αα MAKE POINT POLYHDERA;
XWC(V1) ← ABS(R*0.942809); ZWC(V1) ← -ABS(R/3); αα POSITION FIRST VERTEX;
V2 ← MKEV(F1,V1); ROTATE(V2,0,0,2*PI/3); αα MAKE AND POSITION 2ND VERTEX;
V3 ← MKEV(F1,V2); ROTATE(V3,0,0,2*PI/3); αα MAKE AND POSITION 3RD VERTEX;
V4 ← MKEV(F1,V3); αα MAKE AND POSITION 4TH VERTEX;
XWC(V4)←YWC(V4)←0;ZWC(V4)←ABS(R);
MKFE(V1,F1,V4); F2 ← PFACE(F1); αα CLOSE SKEW QUADRILATERAL;
MKFE(V1,F1,V3); MKFE(V2,F2,V4);
RETURN(B); αα RETURN THE CREATION;
END "MKTETRA";
MKUNIV; MKTETRA(6); αα INITIALIZE AND TEST MKTETRA;
GEODPY; αα DISPLAY REFRESH;
END "EAMPLE FOUR";{λ30;W0,1260,0,1900;JUFA}
Example 5 - Glue two N-edged faces together.{λ7;W100;JAF3}
BEGIN "EXAMPLE FIVE"
REQUIRE "GEOMES.HDR[GEM,HE]" SOURCE_FILE; αα GEOMED EMBEDDED IN SAIL;
DEFINE αα="COMMENT"; DEFINE PI="3.1415927";
INTEGER B1,B2; αα TWO TEST CUBES;
INTEGER PROCEDURE GLUEFF(INTEGER FACE1,FACE2); αα DEMO GLUE FACE TO FACE;
BEGIN "GLUEFF"
INTEGER V,V1,V2,E,E0,I; REAL DMIN,D;
V1 ← VCCW(PED(FACE1),FACE1); αα PICK ONE VERTEX OF FACE1;
αα FIND VERTEX OF FACE2 THAT IS CLOSEST TO V1;
DMIN ← 10@10; E ← E0 ← PED(FACE2); αα INITIALIZE MINIMAL DISTANCE;
DO BEGIN
V ← VCCW(E,FACE2);D ← DISTAN(V1,V); αα SCAN FACE2 FOR VERTEX CLOSEST TO V1;
IF Dα<DMIN THEN BEGIN DMIN←D;V2←V;END;
END UNTIL E0 = (E←ECCW(E,FACE2));
αα MAKE THE WASP EDGE;
E ← GLUEE(FACE1,V1,FACE2,V2); αα FACE2 AND BODY ARE KILLED;
αα CLOSE OTHER EDGES;
V ← OTHER(NCCW(E),V1); αα LAST VERTEX, TO STOP SCAN;
DO BEGIN
V1 ← OTHER(PCW(E),V1); αα FETCH NEXT PAIR OF VERTICES;
V2 ← OTHER(PCCW(E),V2);
E ← MKFE(V1,FACE1,V2); αα CLOSE AN EDGE;
END UNTIL V=V1;
RETURN(BGET(E)); αα RETURN THE SURVIVING BODY;
END "GLUEFF";
MKUNIV; αα INITIALIZATION;
B1 ← MKCUBE(2,2,2); B2 ← MKCUBE(3,3,3); αα TWO TEST CUBES;
ROTATE(B1,0,-PI/2,0);TRANSL(B1,-3,0,0); αα ORIENT CUBES SO FIRST FACES...;
ROTATE(B2,0,+PI/2,0);TRANSL(B2,+4,0,0); αα ...ARE OPPOSITE;
GLUEFF(PFACE(B1),PFACE(B2)); αα TEST THE FUNCTION;
GEODPY; αα DISPLAY REFRESH;
END "EXAMPLE FIVE";{λ30;W0,1260,0,1900;JUFA}